//给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。 
//
// 插入排序 算法的步骤: 
//
// 
// 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 
// 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 
// 重复直到所有输入数据插入完为止。 
// 
//
// 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表
//中。 
//
// 对链表进行插入排序。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入: head = [4,2,1,3]
//输出: [1,2,3,4] 
//
// 示例 2： 
//
// 
//
// 
//输入: head = [-1,5,3,4,0]
//输出: [-1,0,3,4,5] 
//
// 
//
// 提示： 
//
// 
//
// 
// 列表中的节点数在 [1, 5000]范围内 
// -5000 <= Node.val <= 5000 
// 
// Related Topics 链表 排序 👍 488 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

public class _147_InsertionSortList {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new _147_InsertionSortList().new Solution();
        ListNode head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        System.out.print("原始：");
        showList(head);
        System.out.print("排序：");
        ListNode res = solution.insertionSortList(head);
        showList(res);


    }

    private static void showList(ListNode head) {
        if (head == null) {
            System.out.println("empty");
            return;
        }
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
    //leetcode submit region begin(Prohibit modification and deletion)



    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    // 这个是插入排序
    class Solution {
        public ListNode insertionSortList(ListNode head) {
            ListNode sortedHead = new ListNode(-1, head);
            ListNode cur = head.next;
            ListNode pre = head;

            while (cur != null) {
                ListNode sorted = sortedHead;
                while (sorted.next != cur && sorted.next.val < cur.val) {
                    sorted = sorted.next;
                }
                if (sorted.next == cur) {
                    pre = pre.next;
                    cur = cur.next;
                    continue;
                }
                pre.next = cur.next;
                cur.next = sorted.next;
                sorted.next = cur;
                cur = pre.next;
//                pre =
            }
            return sortedHead.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}